/**
 * 
 */
package graph;
import java.util.Queue;
import java.util.Stack;

/**
 * @author michaelyi
 *
 */
public interface GraphAlgorithmsInterface<T> {

	/**
	 * Task: Performs a breadth-first traversal of a graph.
	 * @return a queue of labels of the vertices in the traversal, with
	 * the label of the origin vertex at the queue's front
	 */
	public Queue<T> getBreadthFirstTraversal (T origin);
	
	/**
	 * Task: Performs a depth-first traversal of a graph.
	 * @return a queue of labels of the vertices in the traversal, with
	 * the label of the origin vertex at the queue's front
	 */
	public Queue<T> getDepthFirstTraversal (T origin);
	
	/**
	 * Task: Performs a topological sort of the vertices in a graph 
	 * without cycles.
	 * @return a stack of vertex labels in topological order, beginning
	 * with the stack's top
	 */
	public Stack<T> getTopologicalOrder();
	
	/**
	 * Task: Finds the path between two given vertices that has the shortest 
	 * length.
	 * @param path a stack of labels that is empty initially; at the completion
	 * of the method, this stack contains the labels of the vertices along the
	 * shortest path; the label of the origin vertex is that the top, and the 
	 * label of the destination vertex is at the bottom
	 * @return the length of the shortest path 
	 */
	public int getShortestPath (T begin, T end, Stack<T> path);
	
	/**
	 * Task: Finds the least-cost path between two given vertices.
	 * @return the cost of the cheapest path
	 */
	public double getCheapestPath(T begin, T end, Stack<T> path);
	
	
} // end GraphAlgorithmsInterface
